import java.util.*;

public class Topk {
    //1.前k个最小的
    public static int[] topK(int[] array,int k) {
        //创建一个大根堆
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        //遍历数组前k个放入堆中
        for (int i = 0; i < array.length; i++) {
            if(maxHeap.size() < k) {
                maxHeap.offer(array[i]);
            } else {
                int top = maxHeap.peek();
                if(top < array[i]) {
                    continue;
                } else {
                    maxHeap.poll();
                    maxHeap.offer(array[i]);
                }
            }
        }
        int[] ret = new int[k];
        int i = 0;
        while (k != 0) {
            ret[i] = maxHeap.poll();
            k--;
            i++;
        }
        return ret;
    }
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<List<Integer>> maxheap = new PriorityQueue<>(k, new Comparator<List<Integer>>() {
            @Override
            public int compare(List<Integer> o1, List<Integer> o2) {
                return (o2.get(0)+ o2.get(1))-(o1.get(0)+o1.get(1));
            }
        });
        for (int i = 0; i < Math.min(nums1.length,k); i++) {
            for (int j = 0; j < Math.min(nums2.length,k); j++) {
                if(maxheap.size() < k) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums1[i]);
                    list.add(nums2[j]);
                    maxheap.offer(list);
                } else {
                    List<Integer> list1 = maxheap.peek();
                    int x = list1.get(0)+list1.get(1);
                    if(x < nums1[i]+nums2[j]) {
                        continue;
                    } else {
                        maxheap.poll();
                        List<Integer> list3 = new ArrayList<>();
                        list3.add(nums1[i]);
                        list3.add(nums2[j]);
                        maxheap.offer(list3);
                    }
                    }
                }
        }
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < k && !maxheap.isEmpty(); i++) {
            list.add(maxheap.poll());
        }
        return list;
    }


    public static void main1(String[] args) {
        int[] array = {0,1,2,3,4,5,6,7,8,9};
        int[] ret = topK(array,5);
        for (int i = 0; i < ret.length; i++) {
            System.out.println(array[i]);
        }
    }
}
